home *** CD-ROM | disk | FTP | other *** search
/ Aminet 8 / Aminet 8 (1995)(GTI - Schatztruhe)[!][Oct 1995].iso / Aminet / dev / gcc / gcc270cp.lha / gnu / lib / g++-include / deque.h < prev    next >
C/C++ Source or Header  |  1995-07-28  |  20KB  |  672 lines
  1. /*
  2.  *
  3.  * Copyright (c) 1994
  4.  * Hewlett-Packard Company
  5.  *
  6.  * Permission to use, copy, modify, distribute and sell this software
  7.  * and its documentation for any purpose is hereby granted without fee,
  8.  * provided that the above copyright notice appear in all copies and
  9.  * that both that copyright notice and this permission notice appear
  10.  * in supporting documentation.  Hewlett-Packard Company makes no
  11.  * representations about the suitability of this software for any
  12.  * purpose.  It is provided "as is" without express or implied warranty.
  13.  *
  14.  */
  15.  
  16. #ifndef DEQUE_H
  17. #define DEQUE_H
  18.  
  19. #include <function.h>
  20. #include <algobase.h>
  21. #include <iterator.h>
  22. #include <bool.h>
  23.  
  24. #ifndef Allocator
  25. #define Allocator allocator
  26. #include <defalloc.h>
  27. #endif
  28.  
  29. #ifndef deque 
  30. #define deque deque
  31. #endif
  32.  
  33. template <class T> 
  34. class deque {
  35. public:
  36.     class iterator;
  37.     class const_iterator;
  38.     friend class iterator;
  39.     friend class const_iterator;
  40. public:
  41.     typedef T value_type;
  42.     typedef Allocator<T> data_allocator_type;
  43.     typedef Allocator<T>::pointer pointer;
  44.     typedef Allocator<T>::reference reference;
  45.     typedef Allocator<T>::const_reference const_reference;
  46.     typedef Allocator<T>::size_type size_type;
  47.     typedef Allocator<T>::difference_type difference_type;
  48.     typedef Allocator<pointer> map_allocator_type;   
  49. protected:
  50.     static data_allocator_type data_allocator;
  51. #ifdef __GNUG__
  52.     //    static  // Too bad -- I don't like this hack very much...
  53.     static size_type buffer_size() {
  54.     return data_allocator.init_page_size();
  55.     }
  56. #define __dq_buffer_size buffer_size()
  57. #else
  58.     static size_type buffer_size;
  59. #define __dq_buffer_size buffer_size
  60. #endif
  61.     static map_allocator_type map_allocator;
  62.     typedef Allocator<pointer>::pointer map_pointer;
  63. public:
  64.     class iterator : public random_access_iterator<T, difference_type> {
  65.     friend class deque<T>;
  66.     friend class const_iterator;
  67.     protected:
  68.     pointer current;
  69.     pointer first;
  70.     pointer last;
  71.     map_pointer node;
  72.     iterator(pointer x, map_pointer y) 
  73.         : current(x), first(*y), last(*y + __dq_buffer_size), node(y) {}
  74.     public:
  75.     iterator() : current(0), first(0), last(0), node(0) {}
  76.     reference operator*() const { return *current; }
  77.     difference_type operator-(const iterator& x) const {
  78.         return node == x.node 
  79.         ? current - x.current 
  80.         : difference_type(__dq_buffer_size * (node - x.node - 1) +
  81.                   (current - first) + (x.last - x.current));
  82.     }
  83.     iterator& operator++() {
  84.         if (++current == last) {
  85.         first = *(++node);
  86.         current = first;
  87.         last = first + __dq_buffer_size;
  88.         }
  89.         return *this; 
  90.     }
  91.     iterator operator++(int)  {
  92.         iterator tmp = *this;
  93.         ++*this;
  94.         return tmp;
  95.     }
  96.     iterator& operator--() {
  97.         if (current == first) {
  98.         first = *(--node);
  99.         last = first + __dq_buffer_size;
  100.         current = last;
  101.         }
  102.         --current;
  103.         return *this;
  104.     }
  105.     iterator operator--(int) {
  106.         iterator tmp = *this;
  107.         --*this;
  108.         return tmp;
  109.     }
  110.     iterator& operator+=(difference_type n) {
  111.         difference_type offset = n + (current - first);
  112.         difference_type num_node_to_jump = offset >= 0
  113.         ? offset / __dq_buffer_size
  114.         : -((-offset + __dq_buffer_size - 1) / __dq_buffer_size);
  115.         if (num_node_to_jump == 0)
  116.         current += n;
  117.         else {
  118.         node = node + num_node_to_jump;
  119.         first = *node;
  120.         last = first + __dq_buffer_size;
  121.         current = first + (offset - num_node_to_jump * __dq_buffer_size);
  122.         }
  123.         return *this;
  124.     }
  125.     iterator& operator-=(difference_type n) { return *this += -n; }
  126.     iterator operator+(difference_type n) const {
  127.         iterator tmp = *this;
  128.         return tmp += n;
  129.     }
  130.     iterator operator-(difference_type n) const {
  131.         iterator tmp = *this;
  132.         return tmp -= n;
  133.     }
  134.     reference operator[](difference_type n) { return *(*this + n); }
  135.     bool operator==(const iterator& x) const {      
  136.         return current == x.current || 
  137.         ((current == first || x.current == x.first) && 
  138.          *this - x == 0);
  139.     }
  140.     bool operator<(const iterator& x) const {
  141.         return (node == x.node) ? (current < x.current) : (node < x.node);
  142.     }
  143.     };
  144.     class const_iterator : public random_access_iterator<T, difference_type> {
  145.     friend class deque<T>;
  146.     protected:
  147.     pointer current;
  148.     pointer first;
  149.     pointer last;
  150.     map_pointer node;
  151.     const_iterator(pointer x, map_pointer y) 
  152.         : current(x), first(*y), last(*y + __dq_buffer_size), node(y) {}
  153.     public:
  154.     const_iterator() : current(0), first(0), last(0), node(0) {}
  155.     const_iterator(const iterator& x) 
  156.         : current(x.current), first(x.first), last(x.last), node(x.node) {}     
  157.     const_reference operator*() const { return *current; }
  158.     difference_type operator-(const const_iterator& x) const {
  159.         return node == x.node 
  160.         ? current - x.current 
  161.         : difference_type(__dq_buffer_size * (node - x.node - 1) +
  162.                   (current - first) + (x.last - x.current));
  163.     }
  164.     const_iterator& operator++() {
  165.         if (++current == last) {
  166.         first = *(++node);
  167.         current = first;
  168.         last = first + __dq_buffer_size;
  169.         }
  170.         return *this; 
  171.     }
  172.     const_iterator operator++(int)  {
  173.         const_iterator tmp = *this;
  174.         ++*this;
  175.         return tmp;
  176.     }
  177.     const_iterator& operator--() {
  178.         if (current == first) {
  179.         first = *(--node);
  180.         last = first + __dq_buffer_size;
  181.         current = last;
  182.         }
  183.         --current;
  184.         return *this;
  185.     }
  186.     const_iterator operator--(int) {
  187.         const_iterator tmp = *this;
  188.         --*this;
  189.         return tmp;
  190.     }
  191.     const_iterator& operator+=(difference_type n) {
  192.         difference_type offset = n + (current - first);
  193.         difference_type num_node_to_jump = offset >= 0
  194.         ? offset / __dq_buffer_size
  195.         : -((-offset + __dq_buffer_size - 1) / __dq_buffer_size);
  196.         if (num_node_to_jump == 0)
  197.         current += n;
  198.         else {
  199.         node = node + num_node_to_jump;
  200.         first = *node;
  201.         last = first + __dq_buffer_size;
  202.         current = first + (offset - num_node_to_jump * __dq_buffer_size);
  203.         }
  204.         return *this;
  205.     }
  206.     const_iterator& operator-=(difference_type n) { return *this += -n; }
  207.     const_iterator operator+(difference_type n) const {
  208.         const_iterator tmp = *this;
  209.         return tmp += n;
  210.     }
  211.     const_iterator operator-(difference_type n) const {
  212.         const_iterator tmp = *this;
  213.         return tmp -= n;
  214.     }
  215.     const_reference operator[](difference_type n) { 
  216.         return *(*this + n); 
  217.     }
  218.     bool operator==(const const_iterator& x) const {      
  219.         return current == x.current || 
  220.         ((current == first || x.current == x.first) && 
  221.          *this - x == 0);
  222.     }
  223.     bool operator<(const const_iterator& x) const {
  224.         return (node == x.node) ? (current < x.current) : (node < x.node);
  225.     }
  226.     };
  227.     typedef reverse_iterator<const_iterator, value_type, const_reference, 
  228.                              difference_type>  const_reverse_iterator;
  229.     typedef reverse_iterator<iterator, value_type, reference, difference_type>
  230.         reverse_iterator; 
  231. protected:    
  232.     iterator start;
  233.     iterator finish;
  234.     size_type length;
  235.     map_pointer map;
  236.     size_type map_size;
  237.  
  238.     void allocate_at_begin();
  239.     void allocate_at_end();
  240.     void deallocate_at_begin();
  241.     void deallocate_at_end();
  242.  
  243. public:
  244.     deque() : start(), finish(), length(0), map(0), map_size(0) {
  245. #ifndef __GNUG__
  246.     __dq_buffer_size = data_allocator.init_page_size();
  247. #endif
  248.     }
  249.     iterator begin() { return start; }
  250.     const_iterator begin() const { return start; }
  251.     iterator end() { return finish; }
  252.     const_iterator end() const { return finish; }
  253.     reverse_iterator rbegin() { return reverse_iterator(end()); }
  254.     const_reverse_iterator rbegin() const { 
  255.         return const_reverse_iterator(end()); 
  256.     }
  257.     reverse_iterator rend() { return reverse_iterator(begin()); }
  258.     const_reverse_iterator rend() const { 
  259.         return const_reverse_iterator(begin()); 
  260.     } 
  261.     bool empty() const { return length == 0; }
  262.     size_type size() const { return length; }
  263.     size_type max_size() const { return data_allocator.max_size(); }
  264.     reference operator[](size_type n) { return *(begin() + n); }
  265.     const_reference operator[](size_type n) const { return *(begin() + n); }
  266.     reference front() { return *begin(); }
  267.     const_reference front() const { return *begin(); }
  268.     reference back() { return *(end() - 1); }
  269.     const_reference back() const { return *(end() - 1); }
  270.     void push_front(const T& x) {
  271.     if (empty() || begin().current == begin().first)
  272.         allocate_at_begin();
  273.     --start.current;
  274.     construct(start.current, x);
  275.     ++length;
  276.     }
  277.     void push_back(const T& x) {
  278.     if (empty() || end().current == end().last)
  279.         allocate_at_end();
  280.     construct(finish.current, x);
  281.     ++finish.current;
  282.     ++length;
  283.     }
  284.     void pop_front() {
  285.     destroy(start.current);
  286.     ++start.current;
  287.     --length; 
  288.     if (empty() || begin().current == begin().last)
  289.         deallocate_at_begin();
  290.     }
  291.     void pop_back() {
  292.     --finish.current;
  293.     destroy(finish.current);
  294.     --length; 
  295.     if (empty() || end().current == end().first)
  296.         deallocate_at_end();
  297.     }
  298.     void swap(deque<T>& x) {
  299.     ::swap(start, x.start);
  300.     ::swap(finish, x.finish);
  301.     ::swap(length, x.length);
  302.     ::swap(map, x.map);
  303.     ::swap(map_size, x.map_size);
  304.     }
  305. #ifdef __GNUG__
  306.     iterator insert(iterator position, const T& x) {
  307.     return insert(deque_iterator<T>(position), x);
  308.     }
  309.     deque_iterator<T> insert(deque_iterator<T> position, const T& x);
  310.     void insert(iterator position, size_type n, const T& x) {
  311.     insert(deque_iterator<T>(position), n, x);
  312.     }
  313.     void insert(deque_iterator<T>(position), size_type n, const T& x);
  314. //  template <class Iterator> void insert(iterator position,
  315. //                                        Iterator first, Iterator last);
  316.     void insert(iterator position, const T* first, const T* last) {
  317.     insert(deque_iterator<T>(position), first, last);
  318.     }
  319.     void insert(deque_iterator<T> position, const T* first, const T* last);
  320.     void erase(iterator position) {
  321.     erase(deque_iterator<T>(position));
  322.     }
  323.     void erase(deque_iterator<T> position);
  324.     void erase(iterator first, iterator last) {
  325.     erase(deque_iterator<T>(first), deque_iterator<T>(last));
  326.     }
  327.     void erase(deque_iterator<T> first, deque_iterator<T> last);    
  328. #else
  329.     iterator insert(iterator position, const T& x);
  330.     void insert(iterator position, size_type n, const T& x);
  331. //  template <class Iterator> void insert(iterator position,
  332. //                                        Iterator first, Iterator last);
  333.     void insert(iterator position, const T* first, const T* last);
  334.     void erase(iterator position);
  335.     void erase(iterator first, iterator last);
  336. #endif    
  337.     deque(size_type n, const T& value = T())
  338.     : start(), finish(), length(0), map(0), map_size(0) {
  339. #ifndef __GNUG__
  340.     __dq_buffer_size = data_allocator.init_page_size();  
  341. #endif
  342.     insert(begin(), n, value);
  343.     }
  344. //  template <class Iterator> deque(Iterator first, Iterator last);
  345.     deque(const T* first, const T* last)
  346.     : start(), finish(), length(0), map(0), map_size(0) {
  347. #ifndef __GNUG__
  348.     __dq_buffer_size = data_allocator.init_page_size();  
  349. #endif
  350.     copy(first, last, back_inserter(*this));
  351.     }
  352.     deque(const deque<T>& x)
  353.     : start(), finish(), length(0), map(0), map_size(0) {
  354. #ifndef __GNUG__
  355.     __dq_buffer_size = data_allocator.init_page_size();  
  356. #endif
  357.     copy(x.begin(), x.end(), back_inserter(*this));
  358.     }
  359.     deque<T>& operator=(const deque<T>& x) {
  360.     if (this != &x)
  361.         if (size() >= x.size()) 
  362.         erase(copy(x.begin(), x.end(), begin()), end());
  363.         else 
  364.         copy(x.begin() + size(), x.end(),
  365.              inserter(*this, copy(x.begin(), x.begin() + size(),
  366.                       begin())));
  367.     return *this;
  368.     }
  369.     ~deque();
  370. #ifdef __GNUG__
  371.     friend T* value_type(const iterator&) {
  372.     return (T*)(0);
  373.     }
  374. #endif
  375. };
  376.  
  377. #ifdef __GNUG__
  378. template <class T>
  379. struct deque_iterator: deque<T>::iterator {
  380.     deque_iterator(deque<T>::iterator i) : deque<T>::iterator(i) {}
  381. };
  382.  
  383. template <class T>
  384. inline T* value_type(const deque_iterator<T>&) {
  385.     return (T*)(0);
  386. }
  387. #else
  388. template <class T>
  389. deque<T>::data_allocator_type deque<T>::data_allocator;
  390.  
  391. template <class T>
  392. deque<T>::map_allocator_type deque<T>::map_allocator;
  393.  
  394. template <class T>
  395. deque<T>::size_type deque<T>::__dq_buffer_size = 0; 
  396. // should be data_allocator.init_page_size(); // Borland bug
  397. #endif
  398.  
  399. template <class T>
  400. bool operator==(const deque<T>& x, const deque<T>& y) {
  401.     return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());
  402. }
  403.  
  404. template <class T>
  405. bool operator<(const deque<T>& x, const deque<T>& y) {
  406.     return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
  407. }
  408.  
  409. template <class T>
  410. deque<T>::~deque() { while (!empty()) pop_front(); }     
  411.  
  412. template <class T>
  413. void deque<T>::allocate_at_begin() {
  414.     pointer p = data_allocator.allocate(__dq_buffer_size);
  415.     if (!empty()) {
  416.     if (start.node == map) {
  417.         difference_type i = finish.node - start.node;
  418.         map_size = (i + 1) * 2;
  419. #ifdef __GNU_G__
  420.         map_pointer tmp = map_allocator_type::allocate(map_size);
  421.         copy(start.node, finish.node + 1, tmp + map_size / 4 + 1);
  422.         map_allocator_type::deallocate(map);
  423. #else
  424.         map_pointer tmp = map_allocator.allocate(map_size);
  425.         copy(start.node, finish.node + 1, tmp + map_size / 4 + 1);
  426.         map_allocator.deallocate(map);
  427. #endif
  428.         map = tmp;
  429.         map[map_size / 4] = p;
  430.         start = iterator(p + __dq_buffer_size, map + map_size / 4);
  431.         finish = iterator(finish.current, map + map_size / 4 + i + 1);
  432.     } else {
  433. #ifdef __GNUG__
  434.     map_size = map_allocator_type::init_page_size();
  435.     map = map_allocator_type::allocate(map_size);
  436. #else
  437.         *--start.node = p;
  438.         start = iterator(p + __dq_buffer_size, start.node);
  439. #endif
  440.     }
  441.     } else {
  442. #ifdef __GNUG__
  443.     map_size = map_allocator_type::init_page_size();
  444.     map = map_allocator_type::allocate(map_size);
  445. #else
  446.     map_size = map_allocator.init_page_size();
  447.     map = map_allocator.allocate(map_size);
  448. #endif
  449.     map[map_size / 2] = p;
  450.     start = iterator(p + __dq_buffer_size / 2 + 1, map + map_size / 2);
  451.     finish = start;
  452.     }
  453. }
  454.  
  455. template <class T>
  456. void deque<T>::allocate_at_end() {
  457.     pointer p = data_allocator.allocate(__dq_buffer_size);
  458.     if (!empty()) {
  459.     if (finish.node == map + map_size - 1) {
  460.         difference_type i = finish.node - start.node;
  461.          map_size = (i + 1) * 2;
  462. #ifdef __GNUG__
  463.         map_pointer tmp = map_allocator_type::allocate(map_size);
  464.         copy(start.node, finish.node + 1, tmp + map_size / 4);
  465.         map_allocator_type::deallocate(map);
  466. #else
  467.         map_pointer tmp = map_allocator.allocate(map_size);
  468.         copy(start.node, finish.node + 1, tmp + map_size / 4);
  469.         map_allocator.deallocate(map);
  470. #endif
  471.         map = tmp;
  472.          map[map_size / 4 + i + 1] = p;
  473.         start = iterator(start.current, map + map_size / 4);
  474.         finish = iterator(p, map + map_size / 4 + i + 1);
  475.     } else {
  476.         *++finish.node = p;
  477.         finish = iterator(p, finish.node);
  478.     }
  479.     } else {
  480. #ifdef __GNUG__
  481.     map_size = map_allocator_type::init_page_size();
  482.     map = map_allocator_type::allocate(map_size);
  483. #else
  484.     map_size = map_allocator.init_page_size();
  485.     map = map_allocator.allocate(map_size);
  486. #endif
  487.     map[map_size / 2] = p;
  488.     start = iterator(p + __dq_buffer_size / 2, map + map_size / 2);
  489.     finish = start;
  490.     }
  491. }
  492.  
  493. template <class T>
  494. void deque<T>::deallocate_at_begin() {
  495.     data_allocator.deallocate(*start.node++);
  496.     if (empty()) {
  497.     start = iterator();
  498.     finish = start;
  499. #ifdef __GNUG__
  500.     map_allocator.deallocate(map);
  501. #else
  502.     map_allocator.deallocate(map);
  503. #endif
  504.     } else
  505.     start = iterator(*start.node, start.node);
  506. }
  507.  
  508. template <class T>
  509. void deque<T>::deallocate_at_end() {
  510.     data_allocator.deallocate(*finish.node--);
  511.     if (empty()) {
  512.     start = iterator();
  513.     finish = start;
  514. #ifdef __GNUG__
  515.     map_allocator.deallocate(map);
  516. #else
  517.     map_allocator.deallocate(map);
  518. #endif
  519.     } else
  520.     finish = iterator(*finish.node + __dq_buffer_size, finish.node);
  521. }
  522.  
  523. template <class T>
  524. #ifdef __GNUG__
  525. deque_iterator<T>
  526. deque<T>::insert(deque_iterator<T> posn, const T& x) {
  527.     iterator position = posn;
  528. #else
  529. deque<T>::iterator deque<T>::insert(iterator position, const T& x) {
  530. #endif
  531.     if (position == begin()) {
  532.     push_front(x);
  533.     return begin();
  534.     } else if (position == end()) {
  535.     push_back(x);
  536.     return end() - 1;
  537.     } else if (end() - position > position - begin()) {
  538.     push_front(*begin());
  539.     copy(begin() + 2, position, begin() + 1); 
  540.     *(position - 1) = x;
  541.     return position - 1;
  542.     } else {
  543.     push_back(*(end() - 1));
  544.     copy_backward(position, end() - 2, end() - 1); 
  545.     *position = x;
  546.     return position;
  547.     }
  548. }
  549.  
  550. template <class T>
  551. #ifdef __GNUG__
  552. void deque<T>::insert(deque_iterator<T> posn,
  553.               size_t n, // BAD HACK
  554.               const T& x) {
  555.     iterator position = posn;
  556. #else
  557. void deque<T>::insert(iterator position, size_type n, const T& x) {
  558. #endif
  559.     if (end() - position > position - begin()) {
  560.     iterator old_begin = begin();
  561.     if (n > position - old_begin) {
  562.          size_type m = n - (position - old_begin);
  563.         while (m-- > 0) push_front(x);
  564.         iterator i = position;
  565.         while (i != old_begin) push_front(*--i);
  566.         fill(old_begin, position, x);
  567.     } else {
  568.         iterator i = old_begin + n;
  569.         while (i != old_begin) push_front(*--i);
  570.         copy(old_begin + n, position, old_begin);
  571.         fill(position - n, position, x);
  572.     }
  573.     } else {
  574.     iterator old_end = end();
  575.     if (n > old_end - position) {
  576.          size_type m = n - (old_end - position);
  577.         while (m-- > 0) push_back(x);
  578.         iterator i = position;
  579.         while (i != old_end) push_back(*i++);
  580.         fill(position, old_end, x);
  581.     } else {
  582.         iterator i = old_end - n;
  583.         while (i != old_end) push_back(*i++);
  584.         copy_backward(position, old_end - n, old_end);
  585.         fill(position, position + n, x);
  586.     }
  587.     }
  588. }
  589.  
  590. template <class T>
  591. void deque<T>::insert
  592. #ifdef __GNUG__
  593. (deque_iterator<T> posn, const T* first, const T* last)
  594. {
  595.     iterator position = posn;
  596. #else
  597. (iterator position, const T* first, const T* last)
  598. {
  599. #endif
  600.     size_type n = 0;
  601.     distance(first, last, n);
  602.     if (end() - position > position - begin()) {
  603.     iterator old_begin = begin();
  604.     if (n > position - old_begin) {
  605.          const T* m = last - (position - old_begin);
  606.         while (m != first) push_front(*--m);
  607.         iterator i = position;
  608.         while (i != old_begin) push_front(*--i);
  609.         copy(last - (position - old_begin), last, old_begin);
  610.     } else {
  611.         iterator i = old_begin + n;
  612.         while (i != old_begin) push_front(*--i);
  613.         copy(old_begin + n, position, old_begin);
  614.         copy(first, last, position - n);
  615.     }
  616.     } else {
  617.     iterator old_end = end();
  618.     if (n > old_end - position) {
  619.          const T* m = first + (old_end - position);
  620.         while (m != last) push_back(*m++);
  621.         iterator i = position;
  622.         while (i != old_end) push_back(*i++);
  623.          copy(first, first + (old_end - position), position);
  624.     } else {
  625.         iterator i = old_end - n;
  626.         while (i != old_end) push_back(*i++);
  627.         copy_backward(position, old_end - n, old_end);
  628.         copy(first, last, position);
  629.     }
  630.     }
  631. }
  632.  
  633. template <class T>
  634. #ifdef __GNUG__
  635. void deque<T>::erase(deque_iterator<T> posn) {
  636.     iterator position = posn;
  637. #else
  638. void deque<T>::erase(iterator position) {
  639. #endif
  640.     if (end() - position > position - begin()) {
  641.     copy_backward(begin(), position, position + 1);
  642.     pop_front();
  643.     } else {
  644.     copy(position + 1, end(), position);
  645.     pop_back();
  646.     }
  647. }
  648.     
  649. template <class T>
  650. #ifdef __GNUG__
  651. void deque<T>::erase(deque_iterator<T> fi, deque_iterator<T> la) {
  652.     iterator first = fi;
  653.     iterator last = la;
  654.     difference_type n = last - first;
  655. #else
  656. void deque<T>::erase(iterator first, iterator last) {
  657.      difference_type n = last - first;
  658. #endif
  659.     if (end() - last > first - begin()) {
  660.     copy_backward(begin(), first, last);
  661.     while(n-- > 0) pop_front();
  662.     } else   {
  663.     copy(last, end(), first);
  664.     while(n-- > 0) pop_back();
  665.     }
  666. }
  667.  
  668. #undef Allocator
  669. #undef deque
  670.  
  671. #endif
  672.